package org.basis.algorithm.list.practice;

/**
 * 最长回文子串，这里可以用动态规划降低时间复杂度
 *
 * @author Mr_wenpan@163.com 2021/12/23 11:53
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        final String str = "cbbd";
        String res = longestPalindrome(str);
        System.out.println(res);
    }

    public static String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        String res = "";

        // 从前往后走
        for (int i = 0; i < chars.length; i++) {
            // 从后往前走
            for (int j = chars.length - 1; j >= i; j--) {
                // 相等后两个位置同时向中间走
                if (chars[i] == chars[j]) {
                    int idx1 = i;
                    int idx2 = j;
                    boolean isEnd = true;

                    // 判断从i ~ j中间是否也相等
                    while (idx1 <= idx2 && (idx1 < chars.length) && idx2 >= 0) {
                        if (chars[idx1] == chars[idx2]) {
                            idx1++;
                            idx2--;
                        } else {
                            isEnd = false;
                            break;
                        }
                    }

                    // 退出后判断是否是回文串
                    if (isEnd) {
                        // substring为[x,y)区间，所以要加一
                        String sub = s.substring(i, j + 1);
                        if (sub.length() > res.length()) {
                            res = sub;
                        }
                    }

                }
            }
        }

        return res;
    }
}
